Not Applicable
Not Applicable
The present invention is related to the field of data networks such as Asynchronous Transfer Mode (ATM) networks, and more particularly to flow-control techniques used to control the transmission of data in data networks.
The term xe2x80x9cflow controlxe2x80x9d generally refers to intentional control exercised by network components over data traffic in the network to achieve desired operational results. For example, flow control can be used to minimize or prevent loss of data cells resulting from the overflowing of receive buffers used by various network components to temporarily store data traffic. Flow control can also be used to enforce an agreed-upon transmission capacity, or rate, available to a customer or to a network element carrying traffic from a number of customers.
One known flow-control protocol used in ATM networks is referred to as xe2x80x9cQuantum Flow Controlxe2x80x9d or QFC. The QFC protocol can be applied to network links and/or individual virtual connections to provide a desired quality of service (QOS). One significant feature of the QFC protocol is its ability to guarantee that no transmitted cells are lost, or discarded, due to insufficient buffering at the receive end of a link or connection. To achieve this result, the QFC protocol employs a messaging scheme and associated functionality within participating network elements based on the concept of transmission credits. Transmission credits are maintained in a xe2x80x9cpoolxe2x80x9d data structure at the transmitting end of a link or connection. A credit is consumed for each cell (or group of cells of a predetermined size) transmitted on the link or connection. The credits are replenished in response to explicit messages sent to the transmitter from the receiver. In general, the receiver extends additional credits as the received cells are forwarded out of the receiver""s cell buffer. The transmitter is permitted to transmit cells only as long as there are credits in the pool. If the pool of available credits becomes empty, the transmitter must wait until the next replenishment from the receiver before resuming the transmission of cells.
Another known flow-control protocol used in ATM networks is referred to as xe2x80x9cExplicit Ratexe2x80x9d or ER. The ER protocol utilizes messages to convey rate information explicitly between a transmitter and a receiver. A forward-type message is used by the transmitter to inform the receiver of the actual transmission rate or a currently allowed maximum transmission rate. The receiver uses this information to generate backward-type messages that inform the transmitter whether its actual or allowed maximum transmission rate should be changed, and if so to what value. In turn, the transmitter uses the information in the backward-type messages to control its transmission rate. On a typical bidirectional link, both forward and backward flow-control messages are flowing in each direction between the respective transmitter/receiver pairs.
Connections in an ATM network can be configured in a variety of ways to meet the needs of different traffic types. These types include Constant Bit Rate (CBR), Variable Bit Rate (VBR), Available Bit Rate (ABR) and Unspecified Bit Rate (UBR), these being arranged in descending order of the strictness of their respective transmission requirements. On a CBR connection cells must be transmitted at exactly a specified rate with constant cell spacing. CBR connections are used to carry delay-sensitive data, for example real-time streaming video data. In a VBR connection, cells are transmitted at a specified average cell rate, within a certain specified tolerance. In an ABR connection, cells are transmitted at a generally varying rate maintained between a specified minimum value (which may be zero) and a specified maximum value. For UBR connections, no guarantees are made regarding even a minimum data transmission rate.
Data traffic for each class of connection can be thought of as having two distinct components, one at a xe2x80x9csustainedxe2x80x9d rate and one at a xe2x80x9cvariablexe2x80x9d rate. In a CBR connection, for example, all of the traffic is carried at a sustained rate equal to the specified constant bit rate; the variable component is substantially zero. VBR and ABR connections generally have a non-zero sustained component along with a non-zero variable component, and UBR connections have a zero sustained component. Network devices such as switches take these characteristics into consideration when allocating link transmission bandwidth for connections. That is, bandwidth is allocated in a fixed or scheduled manner for the sustained component of a connection, and in a dynamic manner for the variable component. A transmission time slot is made available for dynamic allocation only if there is no scheduled cell to transmitted. The dynamically-assigned bandwidth generally must be shared by multiple connections. An arbitration mechanism is used to allocate this bandwidth to the connections in a fair manner.
One important aspect of the cell transmission pattern on a connection is the spacing of the cells. For a CBR connection, the spacing is predictable and constant. For a VBR or ABR connection, the cell spacing is more variable. Cell buffering is employed in network devices to accommodate the variability, and flow control may be used to minimize cell loss while maintaining a given data rate. When a VBR or ABR connection is carried on a link along with several other active connections, the cells constituting the variable component of the connection are usually spaced apart by the normal action of the arbitration mechanism. That is, adjacent cells for a given connection are generally separated by a number of cells from the various other connections that share bandwidth on the link.
However, under lighter traffic conditions the cells constituting the variable component of a connection may be susceptible to xe2x80x9cclumpingxe2x80x9d, i.e., transmission in bursts of several cells having little or no spacing. Clumping is a manifestation of what is referred to as xe2x80x9ccell delay variationxe2x80x9d or CDV. The amount of CDV allowed for a connection can be specified by a configuration parameter called cell delay variation tolerance (CDVT). As described below, clumping may have deleterious effects on some network connections. For a CBR connection, or more generally the sustained component of any connection, clumping is avoided by normal cell scheduling operation as described above. However, this mechanism is not available to control clumping of the cells constituting the variable component of a connection.
Connections using the QFC flow-control protocol generally exhibit a high tolerance for cell delay variation. This is because a substantial amount of cell buffer storage is used in order to guarantee zero cell loss in accordance with the QFC specification. This buffer storage inherently accommodates cell clumping.
In contrast, ER connections can be more sensitive to clumping, because the ER protocol does not presuppose the existence of substantial cell buffering as does QFC. Moreover, it is generally the practice to use fixed scheduling only to achieve the minimum cell rate on an ER connection. Most of the traffic has link bandwidth allocated dynamically, and therefore is susceptible to clumping. Accordingly, there is a need for a mechanism to control the degree of clumping or cell delay variation on network links such as ER links that rely considerably on dynamically allocated link bandwidth.
In accordance with the present invention, a method and apparatus are disclosed for controlling the transmission of cells on a connection such that cell clumping is maintained within specified limits. The technique is particularly suited for use with a rate-based flow-control protocol such as the Explicit Rate (ER) protocol.
In each of successive transmission intervals, a number N is calculated that represents the maximum number of cells permitted to be transmitted consecutively. N is calculated based on a generally variable allowed cell rate (ACR) which is prevailing for the connection for the interval. For example, N is the quotient obtained by dividing a predetermined cell delay variation tolerance (CDVT) by the difference between the reciprocal of the ACR and the reciprocal of a link cell rate (LCR). In general, N is less than a number NRM that indicates the maximum number of data cells allowed between ER forward flow-control cells. If the calculated quotient is greater than NRM, N is set equal to NRM.
A value C is then calculated as the largest integer factor of NRM that is no greater than N, and the transmission interval is divided into NRM/C sub-intervals. No more than C cells are allowed to be transmitted on the connection in each of the sub-intervals. In a disclosed network interface module, this limit is enforced through use of a credit mechanism in which no more than C credits are extended to the cell transmitter in each sub-interval.
Through the use of the above technique, cell clumping is kept to within acceptable limits for data link connections that employ a rate-based flow-control protocol such as the Explicit Rate protocol. Additionally, the technique exploits existing control mechanisms used in credit-based flow control protocols such as QFC, and therefore can be used efficiently in logic that provides configurable support for either ER or QFC connections.
Other aspects, features, and advantages of the present invention are disclosed in the detailed description that follows.